\documentclass{beamer}
%grafos
\usepackage[all]{xy}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{multimedia}
\usetheme{Antibes}
\title{Problema do Carteiro Chinês}
\institute{Universidade Federal de Minas Gerais}
\author{
Daniel Brasil\\
João Paulo Pesce\\
Guilherme Maluf\\
Geraldo Franciscani\\
}

\beamertemplateballitem

\definecolor{myblue}{rgb}{0.2, 0.2,0.701960784 }
\setbeamercolor{uppercol}{fg=white,bg=myblue}%

\date{\today}

\AtBeginSection[]
{
\begin{frame}
\frametitle{Sumário}
\tableofcontents[currentsection]
\end{frame}
}

\begin{document}

\begin{frame}
\begin{figure}[hb!]
\includegraphics[scale=0.6]{imagens/ufmg.jpg}
\end{figure}
\maketitle
\end{frame}


\section{Problema do Carteiro Chinês}
\begin{frame}\frametitle{Problema do Carteiro Chinês}
\begin{itemize}
\item Imagine um carteiro
\item Roteiro diário
\item Identificar a maneira de minimizar a distância total percorrida.
\end{itemize}
%O problema consiste em encontrar o menor caminho que um carteiro deve percorrer de forma a passar por todas as ruas da cidade pelo menos uma vez.\\

\includegraphics[scale=0.5]{../doc/imagens/cidade.png}

\end{frame}

\section{Definições}
\begin{frame} 
\frametitle{Definições Formais}

\begin{block}

\begin{enumerate}[<alert@+>]
\item Grau de um Vértice
\item Caminho 
\item Circuito 
\item Grafo Conexo
\item Caminho Euleriano
\item Circuito Euleriano
\item Grafo Euleriano
\end{enumerate}
\end{block}
%\begin{block}{Problema do Carteiro Chinês}
%Busca-se gerar um percurso de custo mínimo sobre um grafo $ G = (V,E) $ , valorado e conexo, a partir de um vértice $v_0 \in V$ , origem;
%\end{block}
%
%\begin{block}{Circuito Euleriano}
%Circuito é dito euleriano se ele contém todas as arestas de um grafo
%\end{block}
%
%\begin{block}{Grafo Euleriano}
%Um grafo conexo G é um grafo euleriano se e somente se todo vértice de G possui grau par. 
%\end{block}
%
\end{frame}

\section{Modelagem}
\begin{frame} \frametitle{Abordagens}
\begin{block}{Percurso de custo minimo a partir de um vértice $v_0 \in V$}
\begin{itemize}%[<alert@+>]
\item <alert@+>Caso Simétrico
\only<1>{
\begin{itemize}
\item grafo $G = (V,E)$
\item valorado
\item conexo
\end{itemize}
}
\item<alert@+> Caso Dirigido 
\only<2>{
\begin{itemize}
\item digrafo $G = (V,A)$
\item valorado
\item f-conexo
\end{itemize}
}
\item<alert@+> Caso Misto
\only<3>{
\begin{itemize}
\item digrafo $G = (V,E,A)$
\item valorado
\item f-conexo
\end{itemize}
}
\item<alert@+> Caso Íngreme
\only<4>{
\begin{itemize}
\item digrafo $G = (V,E)$
\item valorado
\item conexo
\item $c_{ij} \neq c_{ji} \in E$
\end{itemize}
}
  \end{itemize}
\end{block}

\end{frame}

\begin{frame}\frametitle{Modelagem Adotada}
\begin{block}{Modelagem feita através do Caso Simétrico onde}
\begin{itemize}
\item cada aresta é uma rua;
\item vértices são os cruzamentos entre ruas;
\item o peso das arestas é definido pelo tamanho da rua.
\end{itemize}
   
\hspace{4.0cm} \xymatrix{
                                                &  \bullet{\ar@{-}_{4}[d] \ar@{-}^{2}[ddr]}_0  & \\ 
    \bullet{\ar@{-}^{3}[r] \ar@{-}_{7}[d]}_1    & \bullet{\ar@{=}_{6}^{5}[dd]}_2    & \\ 
    \bullet{\ar@{-}^{3}[ur] \ar@{-}^{7}[dr]}_3  &                                   & \bullet{\ar@{-}^{\hspace{0.75cm}12}[ll] \ar@{-}^{12}[dl] \ar@{-}^{3}[ul]}_4 \\
   & {\bullet}_5 & 
}
%\hspace{3.0cm}\includegraphics[scale=0.5]{../doc/imagens/grafo.png}
\end{block}<++>
\end{frame}

\begin{frame}
\frametitle{Algoritmos}
\only<1>{
  \begin{block}{Fleury}
  Encontrar o circuito euleriano num grafo $G$

  \begin{enumerate}
  \item Comece de qualquer vértice G
  \item Vá para qualquer aresta que não seja uma ponte
  \item Delete a aresta selecionada
  \item Se NÃO existe mais arestas PARE, caso contrário volte para o passo 2
  \end{enumerate}

  \hspace{5.0cm}\includegraphics[scale=0.4]{imagens/fleury.jpg}

  \end{block}
}

\only<2>{
\begin{block}{Floyd-Warshall}
Determina a distância entre todos os pares de vértices de um grafo
\begin{itemize}
\item Seja o subconjunto ${1,2,...,k} \in V={1,2,...,n}$, onde $k$ possui maior valor entre os vértices intermediários
\item Para qualquer par de vértices $i,j \in V$ considera-se todos os caminhos de $i \mapsto j$ em que $V_I={1,2,...,k}$
\item $d^{(k)}_{i,j}$ o custo do caminho mais curto entre $i,j$ 
\item $camMin(i,j,k)=min{camMin(i,j,k-1),camMin(i,k,k-1),camMin(k,j,k-1)}$
\end{itemize}
\end{block}
}

\only<3-5>{
  \begin{block}{Emparelhamento}
  Transformar um grafo não-Euleriano em Euleriano adicionando arestas no grafo
  \begin{enumerate}
  \item Liste todos os vértices impares $\in G$
  \item Ache todos os conjuntos possíveis de pares de vértices impares
  \item Para cada conjunto de pares, ache o menor caminho entre os pares.
  \end{enumerate}

  \only<4>{
\hspace{4.0cm}    \xymatrix{
    \bullet{\ar@{-}[r]^7 \ar@{-}[d]^2}_a & \bullet{\ar@{-}[r]^9 \ar@{-}[d]^6}_b  & \bullet{\ar@{-}[dl]_7}_c      \\
    \bullet{\ar@{-}[r]^8 \ar@{-}[dr]^{12}}_f  &  \bullet{\ar@{-}[r]^4  \ar@{-}[d]^4}_g & \bullet{\ar@{-}[dl]^5}_d    \\
        & {\bullet}_e  &    
    }
  }
    \only<5>{
\hspace{4.0cm}    \xymatrix{
    \bullet{\ar@{=}[r]^7 \ar@{=}[d]^2}_a & \bullet{\ar@{-}[r]^9 \ar@{-}[d]^6}_b  & \bullet{\ar@{-}[dl]_7}_c      \\
    \bullet{\ar@{-}[r]^8 \ar@{-}[dr]^{12}}_f  &  \bullet{\ar@{-}[r]^4  \ar@{=}[d]^4}_g & \bullet{\ar@{-}[dl]^5}_d    \\
        & {\bullet}_e  &    
    }
  }
%  \only<7>{
%\scriptsize  
%  Três conjuntos de pares: ${b\and e, f\and g}; {b\and f, e\and g}; \and {b\and g, f\and e}$
%\rowcolors[]{1}{blue!20}{blue!10}
%\begin{tabular}[l!]{ccc}
%Par & Cam. Min & Custo \\\hline
%  b$\and$e & b,g,e  &10 \\
%  f$\and$g & f,g    &8  \\
%  b$\and$f & b,a,f  &9  \\
%  e$\and$g & e,g    &4  \\
%  b$\and$g & b, g   &6  \\
%  f$\and$e & f, e   &12
%\end{tabular}
%}
  \end{block}
}
\end{frame}

\section{Aplicações}
\begin{frame}\frametitle{Aplicações Práticas}
\begin{itemize}[<alert@+>]
\item rotas de ônibus \\
    \only<1>{\includegraphics[scale=0.3]{imagens/onibus.jpg}}
\item coleta de lixo\\
    \only<2>{\includegraphics[scale=0.8]{imagens/lixo.jpg}}
\item snow-plowing\\
    \only<3>{\includegraphics[scale=0.1]{imagens/snow.jpg}}
\item inspeção em linhas de transmissão\\
    \only<4>{\includegraphics[scale=0.3]{imagens/linha.jpg}}
\end{itemize}

\end{frame}

\section{Exemplos}
\begin{frame}
\frametitle{Grafo Euleriano}
\begin{block}{$0 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2 \rightarrow 0$}

\hspace{4.0cm} \xymatrix{
                                                &  \bullet{\ar@{-}_{4}[d] \ar@{-}^{2}[ddr]}_0  & \\ 
    \bullet{\ar@{-}^{3}[r] \ar@{-}_{7}[d]}_1    & \bullet{\ar@{=}_{6}^{5}[dd]}_2    & \\ 
    \bullet{\ar@{-}^{3}[ur] \ar@{-}^{7}[dr]}_3  &                                   & \bullet{\ar@{-}^{\hspace{0.75cm}12}[ll] \ar@{-}^{12}[dl] \ar@{-}^{3}[ul]}_4 \\
   & {\bullet}_5 & 
}
\end{block}

\end{frame}

\begin{frame}
\frametitle{Grafo não-Euleriano}
\begin{block}{Duplicando arestas $(2\perp4), (3\perp5)$}
\hspace{4.0cm} \xymatrix{
                                                &  \bullet{\ar@{-}_{4}[d] \ar@{-}^{2}[ddr]}_0  & \\ 
    \bullet{\ar@{-}^{3}[r] \ar@{-}_{7}[d]}_1    & \bullet{\ar@{-}^{5}[dd]}_2    & \\ 
    \bullet{\ar@{-}^{3}[ur] \ar@{-}^{7}[dr]}_3  &                                   & \bullet{\ar@{-}^{12}[dl] \ar@{-}^{3}[ul]}_4 \\
   & {\bullet}_5 & 
}
\end{block}
\end{frame}

\begin{frame}
\frametitle{Grafo não-Euleriano}
\begin{block}{$0 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 3 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 0 $}
\hspace{4.0cm} \xymatrix{
                                                &  \bullet{\ar@{-}_{4}[d] \ar@{-}^{2}[ddr]}_0  & \\ 
    \bullet{\ar@{-}^{3}[r] \ar@{-}_{7}[d]}_1    & \bullet{\ar@{-}^{5}[dd]}_2    & \\ 
    \bullet{\ar@{-}^{3}[ur] \ar@{=}^{7}[dr]}_3  &                                   & \bullet{\ar@{-}^{12}[dl] \ar@{=}^{3}[ul]}_4 \\
   & {\bullet}_5 & 
}
\end{block}
\end{frame}

\section{Obrigado}
\begin{frame}\frametitle{Obrigado}
%\Huge{Obrigado}
\includegraphics[scale=1]{imagens/alan.jpg}
\end{frame}

\end{document}
